﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0086_UniquePaths : IAlgorithm
    {
        // 62. 不同路径

        // 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
        // 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
        // 问总共有多少条不同的路径？

        // 提示：
        //  1 <= m, n <= 100
        //  题目数据保证答案小于等于 2 * 10^9

        public void Test()
        {
            // 算法参数定义
            int m = 4, n = 4;
            // 算法执行与打印
            Console.WriteLine(UniquePaths1(m, n));
        }

        // 算法
        public int UniquePaths(int m, int n)
        {
            var dp = new int[m, n];
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                    if (i == 0 || j == 0)
                        dp[i, j] = 1;
                    else
                        dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
            return dp[m - 1, n - 1];
        }
        public int UniquePaths1(int m, int n)
        {
            var dp = new int[n - 1];
            for (int i = 0; i < m - 1; i++)
                for (int j = 0; j < n - 1; j++)
                    dp[j] = (j == 0 ? 1 : dp[j - 1]) + (i == 0 ? 1 : dp[j]);
            return dp[n - 2];
        }
    }
}
